/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/next-greater-element-i
   @Language: C++
   @Datetime: 19-05-16 15:47
   */

class Solution {
public:
	/**
	 * @param nums1: an array
	 * @param nums2: an array
	 * @return:  find all the next greater numbers for nums1's elements in the corresponding places of nums2
	 */
	vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
		// Write your code here
		stack<int> s;
		unordered_map<int,int> maxr;
		for(int i=0; i<nums2.size(); s.push(nums2[i++]))
			for(; s.size() && s.top()<nums2[i]; s.pop())
				maxr[s.top()]=nums2[i];
		vector<int> v(nums1.size(),-1);
		for(int i=0; i<nums1.size(); ++i)
			if(maxr.count(nums1[i])) v[i]=maxr[nums1[i]];
		return v;
	}
};
